/**
 * 25. K 个一组翻转链表
 *
 * 【困难】
 *
 * 给你链表的头节点 head ，每 k 个节点一组进行翻转，请你返回修改后的链表。
 * k 是一个正整数，它的值小于或等于链表的长度。如果节点总数不是 k 的整数倍，那么请将最后剩余的节点保持原有顺序。
 * 你不能只是单纯的改变节点内部的值，而是需要实际进行节点交换。
 *
 * 示例 1：
 * 【https://assets.leetcode.com/uploads/2020/10/03/reverse_ex1.jpg】
 * 输入：head = [1,2,3,4,5], k = 2
 * 输出：[2,1,4,3,5]
 *
 * 示例 2：
 *【https://assets.leetcode.com/uploads/2020/10/03/reverse_ex2.jpg】
 * 输入：head = [1,2,3,4,5], k = 3
 * 输出：[3,2,1,4,5]
 */

import { ListNode } from '../utils/list'

function reverseKGroup(head: ListNode | null, k: number): ListNode | null {
	const dummy = new ListNode()
	dummy.next = head
	let curr = head
	let prev = dummy

	while (curr) {
		// 寻找 k 个一组的尾节点
		let tail = prev
		for (let i = 0; i < k; i++) {
			tail = tail.next!
			if (!tail) {
				return dummy.next
			}
		}

		const next = tail.next

		// 翻转子链表
		;[curr, tail] = reverse(curr, tail)

		// 反转后的子链接接回原链表
		prev.next = curr
		tail.next = next

		// 遍历
		prev = tail
		curr = tail.next
	}

	return dummy.next
}

function reverse(curr, tail) {
	let p = curr
	let prev = tail.next

	while (prev != tail) {
		const next = p.next
		p.next = prev

		prev = p
		p = next
	}

	return [tail, curr]
}
